import java.util.ArrayList;
import java.util.List;

public class PathSumII {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root != null){
            List<Integer> path = new ArrayList<>();
            func(root,targetSum,0,path,ans);
        }
        return ans;
    }

    public void func(TreeNode cur, int aim, int sum, List<Integer> path, List<List<Integer>> ans){
        if(cur.left == null && cur.right == null){
            if(cur.val + sum == aim){
                path.add(cur.val);
                copy(path,ans);
                path.remove(path.size()-1);  //复原现场
            }
        }else{
            path.add(cur.val);
            if(cur.left != null) {
                func(cur.left,aim,cur.val + sum,path,ans);
            }
            if(cur.right != null){
                func(cur.right,aim,cur.val + sum,path,ans);
            }
            path.remove(path.size()-1);//复原现场
        }
    }

    public void copy(List<Integer> path, List<List<Integer>> ans){
        List<Integer> newPath = new ArrayList<>();
        for(Integer num : path){
            newPath.add(num);
        }
        ans.add(newPath);
    }
}

